package com.dyz.baseAlgorithm.linkedList;

import java.util.Stack;

/**
 * @author: daiyizheng
 * @date: 2021/4/26 12:42
 * @description:
 */
public class Interview {

    //初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    //返回头节点
    public HeroNode getHead(){
        return head;
    }

    public static void main(String[] args) {
        // 进行测试
        // 先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        // 创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);
        // 加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

//        singleLinkedList.list();
//        // 测试一下 求单链表中有效节点的个数
//        System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));// 2
//        // 测试一下看看是否得到了倒数第K个节点
//        HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
//        System.out.println("res=" + res);
        // 测试一下单链表的反转功能
//        System.out.println("原来链表的情况~~");
//        singleLinkedList.list();
//
//        System.out.println("反转单链表~~");
//        reverseHead(singleLinkedList.getHead());
//        singleLinkedList.list();
          reversePrintf(singleLinkedList.getHead());
    }

    /**
     * 方法：获取到单链表的节点的个数（如果是带头节点的链表，需要不统计头节点）
     * @param head  链表的头节点
     * @return 返回的就是有效节点的个数
     */
    public static int getLength(HeroNode head){
        if(head.next == null){
            return 0;
        }

        int length = 0;
        //定义一个辅助的变量，这里我们没有统计头节点
        HeroNode cur = head.next;
        while (cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 查找单链表中的倒数第k个结点 【新浪面试题】
    // 思路
    // 1. 编写一个方法，接收head节点，同时接收一个index
    // 2. index 表示是倒数第index个节点
    // 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
    // 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
    // 5. 如果找到了，则返回该节点，否则返回nulll
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        //判断如果链表为空，返回null
        if (head.next==null){
            return null;
        }
        //第一个遍历得到链表的长度（节点的个数）
        int size = getLength(head);
        //第二次遍历size-index位置，就是我们倒数的第K个节点
        //先做一个index的校验
        if(index <= 0 || index>size){
            return null;
        }
        //定义给辅助变量， for循环定位到倒数的index
        HeroNode cur = head.next;
        for (int i=0;i<size-index; i++){
            cur = cur.next;
        }
        return cur;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    // (如果有这个排名，则添加失败，并给出提示)
    public void addByOrder(HeroNode heroNode){
        // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;// flag标志添加的编号是否存在，默认为false
        while (true){
            if (temp.next == null){// 说明temp已经在链表的最后
                break;
            }
            if (temp.next.no > heroNode.no) { // 位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) {// 说明希望添加的heroNode的编号已然存在

                flag = true; // 说明编号存在
                break;
            }
            temp = temp.next; // 后移，遍历当前链表
        }
        // 判断flag 的值
        if (flag){
            // 不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    public static void reverseHead(HeroNode head){
        //如果当前链表为空或者只有一个节点，无需反转，直接返回
        if(head.next == null|| head.next.next==null){
            return;
        }
        //定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null; //指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        // 动脑筋
        while(cur!=null){
            next = cur.next; //先暂时保存当前节点的下一个节点，就将其取出，因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;//将cur 链接到新的链表上
            cur = next;//让cur后移
        }
        // 将head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
    }

    public static  void  reverseList(HeroNode head){
        // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
            return;

        }
        //当前节点
        HeroNode cur  = head.next;
        // 下一节点
        HeroNode next = cur.next;
        //首节点反转为尾节点，需要指向 null
        cur.next = null;
        // next == null 时，链表已经反转完毕
        while (next!=null){
            //记录next下一个节点
            HeroNode nnext = next.next;

            //反转链表
            next.next = cur;
            //指针后移
            cur = next;
            next=nnext;
        }
        //最后加上首节点
        head.next = cur;
    }
    // 方式2：
// 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
    public  static void reversePrintf(HeroNode head){
        Stack<HeroNode> stack = new Stack<>();

        if (head.next==null){ // 空链表，不能打印
            System.out.println("链表为空");
        }

        HeroNode cur = head.next;
        while (cur!=null){
            stack.add(cur);  // 将链表的所有节点压入栈
            cur = cur.next; // cur后移，这样就可以压入下一个节点
        }
        while (stack.size()>0){
            System.out.println(stack.pop());  // stack的特点是先进后出
        }
    }
}



